package shuzu;

public class _05连续子数组最大累加和 {
    /**
     * 求和最大的连续子数组,有可能不唯一，返回一个即可
     */
    public static void main(String[] args) {
        int[] a = {1, -2, 3, 5, -2, 6, -1};
        findByForce(a);
        int max = findByUp(a);
        System.out.println(max);
    }

    //暴力法
    public static void findByForce(int[] a) {
        int n = a.length;
        int maxSum = a[0];
        for (int j = 0; j < n; j++) {
            int sum = a[j];
            int maxOfJ = sum;
            for (int i = j + 1; i < n; i++) {
                sum += a[i];
                if (sum > maxOfJ) {
                    maxOfJ = sum;
                }
            }
            if (maxOfJ > maxSum) {
                maxSum = maxOfJ;
            }
        }
        System.out.println(maxSum);
    }

    //递归法
    //依次累加，如果累加的和是负数，说明对后面的计算没有作用，丢弃，如果为正数，保留并继续此操作
    public static int findByUp(int[] a) {
        int sumJ = a[0];
        int maxSum = sumJ;
        for (int i = 1; i < a.length; i++) {
            if (sumJ >= 0) {
                sumJ += a[i];
            } else {
                sumJ = a[i];
            }
            if (sumJ > maxSum) {
                maxSum = sumJ;
            }
        }
        return maxSum;
    }


}
